The present invention relates to a method an apparatus for processing natural language using operations performed on weighted and non-weighted multi-tape automata.
Finite state automata (FSAs) are mathematically well defined and offer many practical advantages. They allow for fast processing of input data and are easily modifiable and combinable by well defined operations. Consequently, FSAs are widely used in Natural Language Processing (NLP) as well as many other fields. A general discussion of FSAs is described in Patent Application Publication U.S. 2003/0004705 A1 and in “Finite State Morphology” by Beesley and Karttunen (CSLI Publications, 2003), which are incorporated herein by reference.
Weighted finite state automata (WFSAs) combine the advantages of ordinary FSAs with the advantages of statistical models, such as Hidden Markov Models (HMMs), and hence have a potentially wider scope of application than FSAs. Weighted multi-tape automata (WMTAs) have yet more advantages. For example, WMTAs permit the separation of different types of information used in NLP (e.g., surface word form, lemma, POS-tag, domain-specific information) over different tapes, and preserve intermediate results of different steps of NLP on different tapes. Operations on WMTAs may be specified to operate on one, several, or all tapes.
While some basic WMTAs operations, such as union, concatenation, projection, and complementary projection, have been defined for a sub-class of non-weighted multi-tape automata (see for example the publication by Kaplan and Kay, “Regular models of phonological rule systems”, in Computational Linguistics, 20(3):331-378, 1994) and implemented (see for example the publication by Kiraz and Grimley-Evans, “Multi-tape automata for speech and language systems: A prolog implementation”, in D. Woods and S. Yu, editors, Automata Implementation, number 1436 in Lecture Notes in Computer Science, Springer Verlag, Berlin, Germany, 1998), there continues to be a need for improved, simplified, and more efficient operations for processing WMTAs to make use of these advantages in natural language processing.
In accordance with the invention, there is provided a method and apparatus for using weighted multi-tape automata (WMTAs) in natural language processing (NLP) that includes morphological analysis, part-of-speech (POS) tagging, disambiguation, and entity extraction. In performing NLP, operations are employed that perform cross-product, auto-intersection, and tape-intersection (i.e., single-tape intersection and multi-tape intersection) of automata. Such operations may be performed using transition-wise processing on weighted or non-weighted multi-tape automata.
In accordance with one aspect of the invention there is provided in a system for processing natural language, a method for intersecting a first tape and a second tape of a multi-tape automaton (MTA) that has a plurality of n tapes and a plurality of paths. The method includes generating a string tuple <s1, . . . , sn> having a string s for each of the n tapes of each path of the MTA and comparing the string sj of the first tape with the string sk of the second tape in the string tuple. If the strings sj and sk equal, the string tuple is retained in the MTA. However, if the strings sj and sk do not equal, the MTA is restructured to remove the string tuple.
In accordance with another aspect of the invention, there is provided in a system for processing natural language, a method for intersecting a first tape and a second tape of an input multi-tape automaton (MTA) that has a plurality of tapes and a plurality of paths. The method includes computing a first limit and a second limit of the input MTA. An output MTA is constructed that intersects the first tape and the second tape using the second limit to delimit its construction. Transitions are removed along paths in the output MTA during construction except for those transitions of paths having similar labels on the first selected tape and the second selected tape. The constructed output MTA is determined to be regular using the first limit. If the output MTA is determined to be regular, then the output MTA is provided as a complete solution to the intersection of the first tape and the second tape of the input MTA. If the output MTA is determined not to be regular, then the output MTA is provided as a partial solution to the intersection of the first tape and the second tape of the input MTA.
It will be appreciated that the present invention has the following advantages over weighted 1-tape or 2-tape processing of automata because it allows for: (a) the separation of different types of information used in NLP (e.g., surface form, lemma, POS-tag, domain-specific information, etc.) over different tapes; (b) the preservation of some or all intermediate results of various NLP steps on different tapes; and (c) the possibility of defining and implementing contextual replace rules referring to different types of information on different tapes.